The present invention relates to computer systems having multiple processors, and more particularly to a method and apparatus for scheduling each process with a processor that can efficiently execute the process.
In a multiple processor computer system that shares information stored in a common system memory, a given process may become active and execute at various times on various processors. This process migration from one processor to another may occur for numerous reasons. The process may be suspended from running on one of the multiple processors while the process is waiting for an input/output operation to complete. When the input/output operation is completed, the waiting process is marked as ready to run and placed on the run queue. From the run queue, the process may be selected by the next available processor of the multiple processors, which is not necessarily the processor that the process was previously executed by before the suspension. The process may also be suspended from running on a processor because the time slice allocated thereto has expired. Once a process' time slice has expired, the process is typically assigned a lower priority and placed on the run queue, where it may be selected by another processor for execution, i.e. it may migrate.
Migration of a process among multiple processors is a fairly recent problem, because system architectures having multiple processor with each processor having a large capacity cache memory associated therewith are fairly new. This system architecture is, however, a common architecture for modern computer systems. Cache memories are included in order reduce system bus data bandwidth and memory data bandwidth requirements. Cache memories reduce data bandwidth requirements by reducing the number of accesses made to the common system memory to fetch instructions or to read or write operands. Cache memories also reduce the cycle time of an average operation because a data transfer between a processor and its local cache memory is faster than a transfer between the same processor and the more distant common system memory, as is well known.
Process migration, however, typically results in a cache miss, instead of a cache match, and a cache miss results in a lengthy load operation from system memory. Each time a process migrates to a new processor, the migration starts with a cache miss that is followed by a subsequent loading of all or part of the process from system memory. Thus, frequent cache misses followed by lengthy loads from system memory have a negative effect on system bus and memory data bandwidths. This is exactly the opposite result desired by implementing a system architecture having multiple processors with large local caches.
Besides the processor time lost with the cache loading, each time a process migrates, the instructions and operands of that process are duplicated and stored in another cache memory. Needlessly duplicated copies of the same process waste limited cache memory space. Further, migration causes unnecessary cache line replacements of soon-to-be-used processes.
To prevent uncontrolled process migration, some computer system providers have included a type of process affinity scheduling as part of their systems software. Unfortunately, solutions that are entirely software based either takes up a considerable amount of processor time and system data bandwidth, or they are considerably less comprehensive and thereby do not achieve substantial gains in performance.
It is an object of the present invention to provide a hardware based affinity scheduling apparatus for a computer system having multiple processors in order to reduce process migration.
It is another object of the present invention to provide a method for operating a hardware based affinity scheduling apparatus for a computer system having multiple processors in order to reduce process migration.